package com.laotang.第_11_章_数学.力扣_172_阶乘后的零的个数;

import java.util.HashMap;
import java.util.Map;

public class _172_factorial_trailing_zeroes {

    // 计算 [1...n] 有多少个因子 5
    // 时间复杂度：O(n)
    // 空间复杂度：O(1)
    public int trailingZeroes1(int n) {
        int ans = 0;
        for (int i = 5; i <= n; i += 5) {
            int x = i;
            while (x > 0) {
                if (x % 5 == 0) {
                    ans++;
                    x /= 5;
                } else break;
            }
        }
        return ans;
    }

    // 时间复杂度：O(logn)
    // 空间复杂度：O(1)
    public int trailingZeroes(int n) {
        int ans = 0;
        while (n > 0) {
            ans += n / 5;
            n /= 5;
        }
        return ans;
    }

    private String dest;
    private int c1, c2;
    private Map<Character, Integer> mapIndex = new HashMap<>();

    public int minimumCost(String src, String dest, int c1, int c2) {
        this.dest = dest;
        this.c1 = c1;
        this.c2 = c2;
        for (int i = 0; i < src.length(); i++) mapIndex.put(src.charAt(i), i);
        return dfs(src.toCharArray(), 0, 0);
    }

    private int dfs(char[] src, int i, int currCost) {
        if (new String(src).equals(dest)) return currCost;
        if (i == src.length) return Integer.MAX_VALUE;

        if (src[i] == dest.charAt(i)) return dfs(src, i + 1, currCost);
        else {
            // 替换
            char tmp = src[i];
            src[i] = dest.charAt(i);
            int leftMinCost = dfs(src, i + 1, currCost + c1);
            src[i] = tmp;

            // 交换
            int idx = mapIndex.get(dest.charAt(i));
            int rightMinCost = Integer.MAX_VALUE;
            if (idx > i) { // 要交换的字符必须在 i 的后面，否则，不能交换
                char c = src[i];
                src[i] = src[idx];
                src[idx] = c;
                rightMinCost = dfs(src, i + 1, currCost + c2);
                c = src[i];
                src[i] = src[idx];
                src[idx] = c;
            }
            return Math.min(leftMinCost, rightMinCost);
        }
    }

    public static void main(String[] args) {
        String src = "123";
        String dest = "231";

        System.out.println(new _172_factorial_trailing_zeroes().minimumCost(src, dest, 2, 3));
    }

}
